package heap;

import java.util.*;

/**
 * @program: play-structure
 * @author: baichen
 * 力扣347：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * 如：
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 参考前面统计频率的类，使用Java提供的优先队列解决，Java提供的默认是最小堆
 * 通过匿名类/lambda表达式实现，不用自己写一个类
 **/
public class TopKFrequent3 {
//    private class Freq{
//        int e, freq;     //元素e和频次freq
//
//        public Freq(int e, int freq) {
//            this.e = e;
//            this.freq = freq;
//        }

//        public int compareTo(Freq another) {
//            //比较频次大小,要跟自己定义的优先队列区分开，自己定义的是最大堆，Java提供的是最小堆
//            if (this.freq < another.freq)
//                return -1;
//            else if (this.freq > another.freq)
//                return 1;
//            else        //频次相等
//                return 0;
//        }
//    }

    //比较器
//    private class FreqComparator implements Comparator<Freq>{
//        @Override
//        public int compare(Freq a, Freq b) {
//            return a.freq-b.freq;
//        }
//    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        //统计频次
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else
                map.put(num, 1);
        }
        //利用优先队列求出前K个元素,默认是最小堆
//        PriorityQueue<Freq> pq = new PriorityQueue<>(new FreqComparator());
        //优先队列可以传入一个构造器作为匿名类
//        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer a, Integer b) {
//                return map.get(a)-map.get(b);   //频次大小
//            }
//        });
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->map.get(a)-map.get(b));
            //遍历map的key，这个key是数组对应的元素
        for (int key : map.keySet()) {
            if (pq.size() < k) {    //队列里面只存放前k个频次的元素
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) { //判断key和堆顶元素对应的频次
                pq.remove();
                pq.add(key);
            }
        }
        //将前K个元素放入LinkedList
        LinkedList<Integer> result = new LinkedList<>();
        while (!pq.isEmpty()) {
            result.add(pq.remove());
        }
        return result;
    }
}
